// 文件名：unordered_set_auth_bloom.cpp
// 目的：将 Bloom Filter 用作快速“可能存在”判定的前置过滤，加速授权 token 校验；
//      若 Bloom 判断可能存在，再用 unordered_set 作精确验证，排除假阳性。
// BloomFilter 说明：
//   - 使用三组哈希（通过不同 seed 混合）映射到 bit 数组；
//   - add(value)：设置三个位；possiblyContains(value)：三位均为 1 则“可能存在”，否则必定不存在；
//   - 位图用 vector<bool> 存储（节省空间，但有位代理开销），也可改为 std::vector<uint8_t>/std::bitset<N>。
// 正负性：
//   - 假阴性：不存在（布隆不会产生假阴性）；
//   - 假阳性：可能存在（由后续精确集合校验确认或拒绝）。
// 复杂度：
//   - Bloom add/lookup：O(k) 位操作（k=哈希次数）；unordered_set contains：均摊 O(1)。
// 注意：
//   - hash 组合使用异或 + 常数混合，示例级别；生产应使用更独立的哈希族（如不同种子下的 xxhash/CityHash）。

#include <functional>
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>

class BloomFilter {
public:
    explicit BloomFilter(std::size_t sizeBits)
        : size_(sizeBits), bits_(sizeBits) {}

    template <typename T>
    void add(const T& value) {
        setBit(hash(value, 0));
        setBit(hash(value, 1));
        setBit(hash(value, 2));
    }

    template <typename T>
    bool possiblyContains(const T& value) const {
        return testBit(hash(value, 0)) &&
               testBit(hash(value, 1)) &&
               testBit(hash(value, 2));
    }

private:
    template <typename T>
    std::size_t hash(const T& value, std::size_t seed) const {
        // 混合 seed 以得到不同哈希
        return std::hash<T>{}(value) ^ (seed * 0x9e3779b97f4a7c15ULL);
    }

    void setBit(std::size_t idx) { bits_[idx % size_] = true; }
    bool testBit(std::size_t idx) const { return bits_[idx % size_]; }

    std::size_t size_;
    std::vector<bool> bits_;
};

int main() {
    std::unordered_set<std::string> allowedTokens;
    allowedTokens.reserve(1024);

    BloomFilter bloom(8'192); // 位图大小（应按目标误判率与数据规模计算）

    // 预热：将授权 token 加入集合并同步到 Bloom
    std::vector<std::string> bootstrap = {
        "alpha-token", "beta-token", "gamma-token"
    };
    for (const auto& token : bootstrap) {
        allowedTokens.insert(token);
        bloom.add(token);
    }

    // 校验逻辑：先用 Bloom 快速拒绝，再用精确集合确认
    auto check = [&](const std::string& token) {
        if (!bloom.possiblyContains(token)) {
            std::cout << token << ": rejected (Bloom filter negative)\n";
            return;
        }
        if (allowedTokens.contains(token)) {
            std::cout << token << ": authorized\n";
        } else {
            std::cout << token << ": rejected (false positive resolved)\n";
        }
    };

    check("alpha-token");
    check("delta-token");
    check("beta-token");
    check("epsilon-token");

    return 0;
}